package Hard;

public class numWaysOfStop {
    public int numWays(int steps, int arrLen) {
        final int MODULO = 1000000007;
        int maxColumn = Math.min(arrLen - 1, steps);
        int[] dp = new int[maxColumn + 1];
        dp[0] = 1;
        for (int i = 1; i <= steps; i++) {
            int[] dpNext = new int[maxColumn + 1];
            for (int j = 0; j <= maxColumn; j++) {
                dpNext[j] = dp[j];
                if (j - 1 >= 0) {
                    dpNext[j] = (dpNext[j] + dp[j - 1]) % MODULO;
                }
                if (j + 1 <= maxColumn) {
                    dpNext[j] = (dpNext[j] + dp[j + 1]) % MODULO;
                }
            }
            dp = dpNext;
        }
        return dp[0];
    }
}

class Solution {
    int mod = (int) 1e9 + 7;

    public int numWays(int steps, int len) {
        int max = Math.min(steps / 2, len - 1);
        int[][] f = new int[steps + 1][max + 1];
        f[steps][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            for (int j = 0; j <= max; j++) {
                f[i][j] = (f[i][j] + f[i + 1][j]) % mod;
                if (j - 1 >= 0)
                    f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod;
                if (j + 1 <= max)
                    f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
}

class SolutionOfTimeOptimization {
    int mod = (int) 1e9 + 7;

    public int numWays(int steps, int len) {
        int max = Math.min(steps / 2, len - 1);
        int[][] f = new int[steps + 1][max + 1];
        f[steps][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            int edge = Math.min(i, max);
            // if (edge != max) System.out.println(edge + " " + max);
            for (int j = 0; j <= edge; j++) {
                f[i][j] = (f[i][j] + f[i + 1][j]) % mod;
                if (j - 1 >= 0)
                    f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod;
                if (j + 1 <= max)
                    f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
}

class SolutionofSpaceoptimization {
    int mod = (int) 1e9 + 7;

    public int numWays(int steps, int len) {
        int max = Math.min(steps / 2, len - 1);
        int[][] f = new int[2][max + 1];
        f[steps & 1][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            int edge = Math.min(i, max);
            int a = i & 1, b = (i + 1) & 1;
            for (int j = 0; j <= edge; j++) {
                f[a][j] = 0;
                f[a][j] = (f[a][j] + f[b][j]) % mod;
                if (j - 1 >= 0)
                    f[a][j] = (f[a][j] + f[b][j - 1]) % mod;
                if (j + 1 <= max)
                    f[a][j] = (f[a][j] + f[b][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
}
